package com.ting.test.algorithms.并查集;

/**
 * There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
 * <p>
 * A province is a group of directly or indirectly connected cities and no other cities outside of the group.
 * <p>
 * You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
 * <p>
 * Return the total number of provinces.
 */
public class 朋友圈问题 {
    public static int findCircleNum(int[][] M) {
        int length = M.length;
        UnionFindByArr unionFindByArr = new UnionFindByArr(length);
        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 1; j < length; j++) {
                if (M[i][j] == 1) {
                    unionFindByArr.union(i, j);
                }
            }
        }
        return unionFindByArr.getSets();

    }
}
